/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/expression-evaluation
   @Language: C++
   @Datetime: 16-02-09 08:58
   */

// Method 1, convert to reverse polish notation, then evaluate
class Solution {
	vector<string> convertRPN(vector<string> &exps, int &i){
		vector<string> res;
		stack<string> opt;
		for(; i<exps.size(); ++i){
			if(isdigit(exps[i][0]) || exps[i].length()>1){
				res.push_back(exps[i]);
				continue;
			}
			if(exps[i][0]=='+' || exps[i][0]=='-'){
				for(; opt.size(); opt.pop())
					res.push_back(opt.top());
				opt.push(exps[i]);
			}
			else if(exps[i][0]=='*' || exps[i][0]=='/'){
				if(opt.size() && (opt.top()[0]=='*'||opt.top()[0]=='/')){
					res.push_back(opt.top());
					opt.pop();
				}
				opt.push(exps[i]);
			}
			else if(exps[i][0]=='('){
				const auto tmp=convertRPN(exps, ++i);
				res.insert(res.end(),tmp.begin(),tmp.end());
			}
			else if(exps[i][0]==')') break;
		}
		for(; opt.size(); opt.pop())
			res.push_back(opt.top());
		return res;
	}

public:
	/**
	 * @param expression: a list of strings
	 * @return: an integer
	 */
	int evaluateExpression(vector<string> &expression) {
		// write your code here
		int i=0;
		vector<string> exps=convertRPN(expression,i);
		stack<int> s;
		for(const auto &t:exps){
			if(isdigit(t[0]) || t.length()>1) {
				s.push(atoi(t.c_str()));
				continue;
			}
			int b=s.top(); s.pop();
			int a=s.top(); s.pop();
			switch(t[0]){
				case '+' : s.push(a+b); break;
				case '-' : s.push(a-b); break;
				case '*' : s.push(a*b); break;
				case '/' : s.push(a/b); break;
				default : break;
			}
		}
		return s.size()?s.top():0;
	}
};

// Method 2, using increasing stack to convert RPN
class Solution {
	typedef pair<string,int> Node;
	void add(stack<Node> &s, vector<string> &res, Node cur){
		for(; s.size() && s.top().second>=cur.second; s.pop())
			res.push_back(s.top().first);
		s.push(cur);
	}
	vector<string> convertToRPN(vector<string> &exps) {
		// write your code here
		stack<Node> s;
		vector<string> res;
		for(int weight=0, i=0; i<exps.size(); ++i){
			if(isdigit(exps[i][0]) || exps[i].length()>1)
				add(s,res,{exps[i],3+weight});
			else if(exps[i][0]=='+' || exps[i][0]=='-')
				add(s,res,{exps[i],1+weight});
			else if(exps[i][0]=='*' || exps[i][0]=='/')
				add(s,res,{exps[i],2+weight});
			else if(exps[i][0]=='(') weight+=2;
			else if(exps[i][0]==')') weight-=2;
		}
		add(s,res,{"",0});
		return res;
	}

public:
	/**
	 * @param expression: a list of strings
	 * @return: an integer
	 */
	int evaluateExpression(vector<string> &expression) {
		// write your code here
		vector<string> exps=convertToRPN(expression);
		stack<int> s;
		for(const auto &t:exps){
			if(isdigit(t[0]) || t.length()>1) {
				s.push(atoi(t.c_str()));
				continue;
			}
			int b=s.top(); s.pop();
			int a=s.top(); s.pop();
			switch(t[0]){
				case '+' : s.push(a+b); break;
				case '-' : s.push(a-b); break;
				case '*' : s.push(a*b); break;
				case '/' : s.push(a/b); break;
				default : break;
			}
		}
		return s.size()?s.top():0;
	}
};

// Method 3, using increasing stack to convert expression tree
class Solution {
	class ExpressionTreeNode {
		public:
			string symbol;
			ExpressionTreeNode *left, *right;
			ExpressionTreeNode(string symbol) {
				this->symbol = symbol;
				this->left = this->right = NULL;
			}
	};
	typedef pair<ExpressionTreeNode*,int> ETNode;
	ExpressionTreeNode *add(stack<ETNode> &s, ETNode cur){
		ETNode prev(NULL,0);
		for(; s.size() && s.top().second>=cur.second; s.pop()){
			const auto &top=s.top();
			if(prev.first) top.first->right=prev.first;
			prev=top;
		}
		cur.first->left=prev.first;
		s.push(cur);
		return cur.first->left;
	}
	ExpressionTreeNode * build(vector<string> &exps) {
		// write your code here
		stack<ETNode> s;
		for(int weight=0, i=0; i<exps.size(); ++i){
			if(isdigit(exps[i][0]) || exps[i].length()>1)
				add(s,{new ExpressionTreeNode(exps[i]),3+weight});
			else if(exps[i][0]=='+'||exps[i][0]=='-')
				add(s,{new ExpressionTreeNode(exps[i]),1+weight});
			else if(exps[i][0]=='*'||exps[i][0]=='/')
				add(s,{new ExpressionTreeNode(exps[i]),2+weight});
			else if(exps[i][0]=='(') weight+=2;
			else if(exps[i][0]==')') weight-=2;
		}
		ExpressionTreeNode etn("");
		return add(s,{&etn,0});
	}

	int postorder(ExpressionTreeNode *root){
		if(root==NULL) return 0;
		int left=postorder(root->left);
		int right=postorder(root->right);
		if(isdigit(root->symbol[0]) || root->symbol.length()>1)
			return atoi(root->symbol.c_str());
		switch(root->symbol[0]){
			case '+' : return left+right;
			case '-' : return left-right;
			case '*' : return left*right;
			case '/' : return left/right;
		}
		return 0;
	}
public:
	/**
	 * @param expression: a list of strings
	 * @return: an integer
	 */
	int evaluateExpression(vector<string> &expression) {
		// write your code here
		ExpressionTreeNode *root=build(expression);
		return postorder(root);
	}
};
